package string;

import java.util.Arrays;

/**
 * 给你一个字符串 word 和一个整数 k。
 * 如果 |freq(word[i]) - freq(word[j])| <= k 对于字符串中所有下标 i 和 j  都成立，则认为 word 是 k 特殊字符串。
 * 此处，freq(x) 表示字符 x 在 word 中的出现频率，而 |y| 表示 y 的绝对值。
 * 返回使 word 成为 k 特殊字符串 需要删除的字符的最小数量。
 * <p>
 * 示例 1：
 * 输入：word = "aabcaba", k = 0
 * 输出：3
 * 解释：可以删除 2 个 "a" 和 1 个 "c" 使 word 成为 0 特殊字符串。word 变为 "baba"，此时 freq('a') == freq('b') == 2。
 * <p>
 * 示例 2：
 * 输入：word = "dabdcbdcdcd", k = 2
 * 输出：2
 * 解释：可以删除 1 个 "a" 和 1 个 "d" 使 word 成为 2 特殊字符串。word 变为 "bdcbdcdcd"，此时 freq('b') == 2，freq('c') == 3，freq('d') == 4。
 * <p>
 * 示例 3：
 * 输入：word = "aaabaaa", k = 2
 * 输出：1
 * 解释：可以删除 1 个 "b" 使 word 成为 2特殊字符串。因此，word 变为 "aaaaaa"，此时每个字母的频率都是 6。
 *
 * @author Jisheng Huang
 * @version 20250621
 */
public class MinimumDeletions_3085 {
    /**
     * 题意：保证 |word 中任意两个字符的频次的差| <= k
     * 思路：
     * 设 count 为各字符在 word 中的频次。
     * 对于每个 count[i]，都存在两种方案：
     * ※ 删除 count[i]。
     * ※ 保留 count[i]，然后减小 count[i+1,m-1] 以满足条件。
     * 因此，我们可以对 count 排序，然后枚举要保留的部分 count[i,m-1]，
     * 并计算该情况下所需删除的字符数，取最小值即可。
     * <p>
     * 假设要保留 count[i,m-1]，那么 所需删除的字符数 = count[i,m-1] 中减少的部分 + count[0,i-1] 的全部。
     * 其中 count[i,m-1] 中减少的部分为：
     * 将 count[i,m-1] 中 > count[i]+k 的元素减小为 count[i]+k。
     * 那么，假设 count[j] 为 count[i,m-1] 中首个 > count[i]+k 的元素，
     * 则 count[i,m-1] 中减少的部分 为:
     * sum(count[j,m-1]) - (m-j) * (count[i]+k)
     * 因此 所需删除的字符数 = sum(count[j,m-1]) - (m-j) * (count[i]+k) + sum(count[0,i-1])
     * 特别的，由于 i 递增，因此 sum(count[j,m-1]) 和 sum(count[0,i-1]) 都可以通过上一次的值得到。
     */
    public static int minimumDeletions(String word, int k) {
        int m = 26;
        int[] count = new int[m];

        for (int i = 0; i < word.length(); ++i) {
            char c = word.charAt(i);
            ++count[c - 'a'];
        }

        // 排序 count
        Arrays.sort(count);
        // sum(count[j,m-1]) 和 sum(count[0,i-1])
        int suffix = 0;
        int prefix = 0;

        for (int i : count) {
            suffix += i;
        }

        int min = word.length();

        for (int i = 0, j = 0; i < m; ++i) {
            if (count[i] == 0) {
                continue;
            }

            // 令 j 指向 count[i,m-1] 中首个 > count[i] + k 的位置
            // 并更新 suffix
            while (j < m && count[j] <= k + count[i]) {
                suffix -= count[j++];
            }

            // 删除的字符数 = sum(count[j,m-1]) - (m-j) * (count[i]+k) + sum(count[0,i-1])
            int delete = suffix - (m - j) * (count[i] + k) + prefix;
            min = Math.min(min, delete);
            prefix += count[i];
        }

        return min;
    }

    public static void main(String[] args) {
        System.out.println(minimumDeletions("aabcaba", 0));
        System.out.println(minimumDeletions("dabdcbdcdcd", 2));
        System.out.println(minimumDeletions("aaabaaa", 2));
    }
}
